1. Field of the Invention
The present invention relates in general to data processing systems and, in particular, to a superscalar processor for improving the accuracy of predictions of execution of a plurality of conditional branch instructions. Still more particularly, the present invention relates to a superscalar processor for improving the accuracy of predictions of execution of a plurality of conditional branch instructions by detecting aliasing in a branch history table.
2. Description of the Related Art
A superscalar data processing system is a data processing system which includes a microprocessor architecture which is capable of executing multiple instructions per clock cycle. In order to execute multiple instructions per clock cycle, multiple independent functional units that can execute concurrently are required. These multiple instructions may be executed in their original sequence, or out of order in a sequence which is different in some way from the original sequence.
A programmer writes code in a particular sequence. The code may include various branch, or jump, instructions. Branch instructions cause a departure during the execution of instructions from the original sequential order of the instructions. One method for increasing the speed of of instructions is to predict the likely outcome of the execution of a conditional branch instruction. A prediction is made as to whether or not a branch will be taken the next time this conditional branch instruction is executed.
A branch history table, also called a branch prediction buffer, may be maintained within a processor which is a small amount of memory which tracks whether or not a branch was taken the last time it was executed. Therefore, for a particular conditional branch instruction, if the last time this conditional branch instruction was taken, a prediction will be made that the next time the conditional branch instruction is executed it will again be taken.
A conditional branch instruction is associated with one entry of the branch history table. Typically, programs will have a large number of conditional branch instructions. Because the branch history table is a small block of memory, there are not enough entries in the table to map to only one conditional branch instruction for each entry. Therefore, some entries in the branch history table may have two or more associated conditional branch instructions. This can result in mispredictions because it is not known for which conditional branch instruction the current prediction is made.
Therefore a need exists for a data processing system and method for improving the accuracy of predictions of conditional branch instructions where the system includes a branch history table having a plurality of entries, some of which are associated with at least two of the conditional branch instructions.
A data processing system and method are disclosed for improving the accuracy of predictions of a plurality of conditional branch instructions by detecting branch aliasing. A branch history table is established within the processor which includes a plurality of entries. Some of the plurality of entries are associated with at least two of the conditional branch instructions. An aliasing table is established within the processor which includes a plurality of entries. Each of the plurality of aliasing table entries is associated with only one of the plurality of conditional branch instructions. Prior to executing one of the plurality of conditional branch instructions, an outcome of the execution of the one of the plurality of conditional branch instructions is predicted utilizing one of the plurality of branch history table entries associated with the one of the plurality of conditional branch instructions. An outcome of the execution of the one of the plurality of conditional branch instructions is also predicted utilizing one of the plurality of aliasing table entries which is associated with the one of the plurality of conditional branch instructions. Branch aliasing is detected by comparing the prediction made utilizing the branch history table with the prediction made utilizing the aliasing table. In response to the predictions being different, a determination is made that branch aliasing occurred. The prediction made utilizing the aliasing table is then utilized for predicting the outcome of the execution of the one of the plurality of conditional branch instructions.
The above as well as additional objectives, features, and advantages of the present invention will become apparent in the following detailed written description.